# 53.最大子数组和
# 给你一个整数数组nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
# 子数组是数组中的一个连续部分。
#
# 示例1：
# 输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# 输出：6
# 解释：连续子数组[4, -1, 2, 1]的和最大，为6 。
#
# 示例2：
# 输入：nums = [1]
# 输出：1
#
# 示例3：
# 输入：nums = [5, 4, -1, 7, 8]
# 输出：23


class Solution:
    def maxSubArray(self, nums: [int]) -> int:
        res = float('-inf')
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > res: # 取区间累计的最大值（相当于不断确定最大子序终止位置）
                res = count
            if count < 0: # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
                count = 0
        return res

    def maxSubArray2(self, nums: [int]) -> int:
        # dp写法
        if len(nums) == 0:
            return 0
        dp = []
        dp.append(nums[0])
        res = dp[0]
        for i in range(1,len(nums)):
            dp.append(max(dp[i-1]+nums[i],nums[i]))
            if dp[i] > res:
                res = dp[i]
        return res

if __name__ == '__main__':
    nums = [5, 4, -1, 7, 8]
    # nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    tmp = Solution()
    # res = tmp.maxSubArray(nums)
    res = tmp.maxSubArray2(nums)
    print(res)